package leetcode.solution;

import leetcode.struct.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

     For example:
     Given binary tree {3,9,20,#,#,15,7},
     3
     / \
     9  20
     /  \
     15   7
     return its zigzag level order traversal as:
     [
     [3],
     [20,9],
     [15,7]
     ]
 * Created by tanlee on 2016/5/2.
 */
public class BinaryTreeZigzagLevelOrderTraversal {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> cacheList = new LinkedList<TreeNode>();
        boolean flag = false; //为真时,显示的数据是
        if(root == null){
            return resultList;
        }
        cacheList.add(root);
        while(cacheList != null && cacheList.size() != 0){
            LinkedList<TreeNode> nextList = new LinkedList<TreeNode>();
            List<Integer> tempList = new ArrayList<Integer>();
            //这句话是核心,一旦使用这个问题,一旦数据结构修改,里面的大小也会有变化
            int size = cacheList.size();
            for(int i=0;i<size;i++){
                // true 逆读 从右到左 依次放在头结点上
                if(flag){
                    TreeNode tempNode = cacheList.pollLast();
                    tempList.add(tempNode.val);
                    if(tempNode.right != null){
                        nextList.addFirst(tempNode.right);
                    }
                    if(tempNode.left != null){
                        nextList.addFirst(tempNode.left);
                    }
                }
                // false 顺读 从左到右 依次放在后面的节点上
                else{
                    TreeNode tempNode = cacheList.pollFirst();
                    tempList.add(tempNode.val);
                    if(tempNode.left != null){
                        nextList.addLast(tempNode.left);
                    }
                    if(tempNode.right != null){
                        nextList.addLast(tempNode.right);
                    }
                }
            }
            // 翻转结果
            flag = !flag;
            resultList.add(tempList);
            cacheList = nextList;
        }
        return resultList;
    }

}
